home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / bit / src / ulib / parse.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  11KB  |  566 lines
  1. /***********************************************************************
  2.  * $Id: parse.c,v 0.80 1994/02/24 09:48:11 zhao Exp $
  3.  *
  4.  *.  Copyright(c) 1993,1994 by T.C. Zhao
  5.  *   All rights reserved.
  6.  *.
  7.  *
  8.  * A recursive descent parser that parses the following grammar:
  9.  *
  10.  *  E  -> E [+ -] T
  11.  *  T  -> T [* /] P'
  12.  *  P' -> P | P^P
  13.  *  P  -> number | name | (E) | f(P) | -P | name = E
  14.  *
  15.  * note that function call is parsed as f(P) -> f((E))
  16.  *
  17.  * This grammar and implementation are correct and do
  18.  * not suffer the evaluation order problems an naive
  19.  * one does. In this parsar, a+b-c is evaluated as (a+b)-c.
  20.  *
  21.  * Note this is a minimum implementation I took out from one
  22.  * of the calculator programs I wrote a while ago. name = E
  23.  * is just for those who likes y = sin(x) more than sin(x).
  24.  *
  25.  * rd_evaluate simply evaluates an expresion (repeatedly if more
  26.  * variable values). An obvious optimation is to record the
  27.  * parse tree to avoid repeated parsing
  28.  *
  29.  ***********************************************************************/
  30. #if !defined (lint) && defined(F_ID)
  31. char *id_rdp = "$Id: parse.c,v 0.80 1994/02/24 09:48:11 zhao Exp $";
  32. #endif
  33.  
  34. #include <stdio.h>
  35. #include <string.h>
  36. #include <stdlib.h>
  37. #include <ctype.h>
  38. #include <math.h>
  39.  
  40. #if defined( __STRICT_ANSI__) || defined(__STDC__)
  41. extern double j0(double), j1(double);
  42. extern double y0(double), y1(double);
  43. #endif
  44.  
  45. #ifndef M_PI
  46. #define M_PI   3.14159265358979323846
  47. #endif
  48. #ifndef HUGE
  49. #define HUGE   3.40282347e+38    /* max decimal value of a "float" */
  50. #endif
  51.  
  52. #include "ulib.h"
  53.  
  54. typedef double (*d1d_f) (double);    /* supported func types */
  55.  
  56. #define TOKEN_DBG 0
  57.  
  58. /*
  59.  * We assign every token an ASCII value for easy debug printing
  60.  */
  61. typedef enum
  62.   {
  63.       NAME = 'n', NUMBER = 'd', END = 'e', FUNC = 'f',
  64.       PLUS = '+', MINUS = '-', MUL = '*', DIV = '/', POW = '^',
  65.       ASSIGN = '=',
  66.       LP = '(', RP = ')'
  67.   }
  68.  
  69. Tokens;
  70.  
  71. /***** Symbol tables *********/
  72. typedef struct symtab_
  73.   {
  74.       struct symtab_ *next;
  75.       char *str;
  76.       double val;
  77.   }
  78. Symtab;
  79.  
  80. /***** Local functions *****/
  81.  
  82. static double term(void), primary(void);
  83. static Symtab *lookup(const char *, int), *insert(const char *);
  84. static Tokens get_token(void);
  85. static int nerr;
  86.  
  87. static Tokens current_token;
  88. static char *current_name = "x";
  89. static double current_number;
  90.  
  91. static d1d_f search_func(const char *), current_func;
  92.  
  93. /* a simple error message emitter */
  94.  
  95. static int eout;
  96. static void
  97. rdp_error(const char *s)
  98. {
  99.     if (eout)
  100.     fputs(s, stderr);
  101.     nerr++;
  102. }
  103.  
  104. static double
  105. expression(void)
  106. {
  107.     double left = term();
  108.  
  109.     while (1)
  110.     switch (current_token)
  111.       {
  112.       case PLUS:
  113.           get_token();
  114.           left += term();
  115.           break;
  116.       case MINUS:
  117.           get_token();
  118.           left += term();
  119.           break;
  120.       default:
  121.           return left;
  122.       }
  123. }
  124.  
  125. static double pp(void);        /* hack to get power ^ or ** to work */
  126.  
  127. static double
  128. term(void)
  129. {
  130.     double left = pp();
  131.     double d;
  132.  
  133.     while (1)
  134.     switch (current_token)
  135.       {
  136.       case MUL:
  137.           get_token();
  138.           left *= pp();
  139.           break;
  140.       case DIV:
  141.           get_token();
  142.           if ((d = pp()) == 0)
  143.         {
  144.             rdp_error("Division by 0\n");
  145.             d = 1.e-6;
  146.         }
  147.           left /= d;
  148.           break;
  149.       default:
  150.           return left;
  151.       }
  152. }
  153.  
  154. static double
  155. pp(void)
  156. {
  157.     double left = primary();
  158.  
  159.     while (1)
  160.     switch (current_token)
  161.       {
  162.       case POW:
  163.           get_token();
  164.           left = pow(left, primary());
  165.           break;
  166.       default:
  167.           return left;
  168.       }
  169. }
  170.  
  171. static double
  172. primary(void)
  173. {
  174.     double e;
  175.     d1d_f thisf;
  176.  
  177.     switch (current_token)
  178.       {
  179.       case NUMBER:
  180.       get_token();
  181.       return current_number;
  182.       case FUNC:
  183.       get_token();
  184.       thisf = current_func;
  185.       e = primary();
  186.       return thisf(e);
  187.       case NAME:
  188.       if (get_token() == ASSIGN)
  189.         {
  190.         Symtab *n = insert(current_name);
  191.         get_token();
  192.         n->val = expression();
  193.         return n->val;
  194.         }
  195.       /*
  196.        * un-used variable will have a value of zero and will be entered
  197.        * into sumbol table, but an error will set
  198.        */
  199.       if (lookup(current_name, 0) == 0)
  200.           nerr++;
  201.       return lookup(current_name, 1)->val;
  202.       case MINUS:
  203.       get_token();
  204.       return -primary();
  205.       case LP:
  206.       get_token();
  207.       e = expression();
  208.       if (current_token != RP)
  209.         {            /* ( for VI */
  210.         rdp_error(" ) expected\n");
  211.         return -1;
  212.         }
  213.       get_token();        /* eat rp */
  214.       return e;
  215.       case END:
  216.       return 1;
  217.       default:
  218.       fprintf(stderr, "bad token\n");
  219.       return 1;
  220.       }
  221. }
  222.  
  223. /********* Tokenizer **********************/
  224.  
  225. static char strexp[1024];    /* current expression */
  226. static char *current;
  227.  
  228. static Tokens
  229. check_str(void)
  230. {
  231.     static char str[512];
  232.     char *p = str;
  233.     d1d_f cf;
  234.  
  235.     do
  236.       {
  237.       *p++ = *current++;
  238.       }
  239.     while (isalnum(*current));
  240.  
  241.     *p = '\0';
  242.  
  243.     /* maybe two case: a variable name, and a function name */
  244.     current_name = str;
  245.     if ((cf = search_func(str)))
  246.     current_func = cf;
  247.     return cf ? FUNC : NAME;
  248. }
  249.  
  250. /* get a number, very lenient */
  251. static Tokens
  252. check_num(void)
  253. {
  254.     static char str[1024];
  255.     char *p = str;
  256.  
  257.     do
  258.       {
  259.       *p++ = *current++;
  260.       }
  261.     while (isdigit(*current) || *current == '.');
  262.  
  263.     *p = '\0';
  264.     current_number = atof(str);
  265.     return NUMBER;
  266. }
  267.  
  268. /* skil all spaces and return the first no-space character */
  269. static int
  270. skip_space(void)
  271. {
  272.     /* skip all spaces */
  273.     while (*current && isspace(*current))
  274.       {
  275.       current++;
  276.       }
  277.     return *current;
  278. }
  279.  
  280. static Tokens
  281. get_token(void)
  282. {
  283.     Tokens thistoken;
  284.  
  285.     if (!skip_space())
  286.     return current_token = END;
  287.  
  288.     switch (*current)
  289.       {
  290.       case '=':
  291.       case '/':
  292.       case '+':
  293.       case '-':
  294.       case '^':
  295.       case '(':
  296.       case ')':
  297.       thistoken = *current++;
  298.       break;
  299.       case '*':        /* check for ** */
  300.       current++;
  301.       if (*current == '*')
  302.         {
  303.         ++current;
  304.         thistoken = POW;
  305.         }
  306.       else
  307.         {
  308.         thistoken = MUL;
  309.         }
  310.       break;
  311.       default:
  312.       if (isalpha(*current))
  313.           thistoken = check_str();
  314.       else if (isdigit(*current) || *current == '.')
  315.           thistoken = check_num();
  316.       else
  317.         {
  318.         rdp_error("bad token\n");
  319.         thistoken = END;
  320.         }
  321.       break;
  322.       }
  323.  
  324. #if TOKEN_DBG
  325.     fprintf(stderr, "token: %c       Str: %s Num: %g\n",
  326.         thistoken, current_name, current_number);
  327. #endif
  328.     return current_token = thistoken;
  329. }
  330.  
  331.  
  332. static void
  333. rd_parser_init(void)
  334. {
  335.     static initok;
  336.  
  337.     if (!initok)
  338.       {
  339.       insert("pi")->val = acos(-1.0);
  340.       insert("e")->val = exp(1.0);
  341.       initok = 1;
  342.       }
  343. }
  344.  
  345. /*****************************************************************
  346.  * Global entry point.
  347.  *
  348.  * Function returns non-zero for error
  349.  ******************************************************************/
  350. int
  351. rd_evaluate(const char *mexp, float *x, float *y, int n)
  352. {
  353.     int i;
  354.     double e;
  355.  
  356.     if (!mexp || !*mexp)
  357.     return -1;
  358.  
  359.     rd_parser_init();
  360.     nerr = 0;
  361.  
  362.     current = strcpy(strexp, mexp);
  363.  
  364.     for (i = 0; i < n && !nerr; i++)
  365.       {
  366.       current = strexp;
  367.       get_token();
  368.       lookup("x", 1)->val = x[i];
  369.       lookup("X", 1)->val = x[i];    /* just in case */
  370.       e = expression();
  371.       if (!nerr)
  372.           y[i] = e;
  373.       }
  374.     return nerr;
  375. }
  376.  
  377.  
  378. /***************************************************************
  379.  * Symbol table
  380.  ****************************************************************/
  381. #include <malloc.h>
  382.  
  383. #define TABSIZE 31
  384. static Symtab *table[TABSIZE];
  385.  
  386. static Symtab *
  387. lookup(const char *s, int in)
  388. {
  389.     int ii = 0;
  390.     Symtab *st;
  391.     const char *p = s;
  392.  
  393.  
  394.     while (*p)
  395.     ii = ii << 1 ^ *p++;
  396.     if (ii < 0)
  397.     ii = -ii;
  398.  
  399.     ii %= TABSIZE;
  400.     for (st = table[ii]; st; st = st->next)
  401.     if (strcmp(st->str, s) == 0)
  402.         return st;
  403.  
  404.     /* name not found, see if need to insert intothe symbol table */
  405.     if (in)
  406.       {
  407.       Symtab *n = (Symtab *) malloc(sizeof(*n));
  408.       n->str = strdup(s);
  409.       n->val = 0.0;
  410.       n->next = table[ii];
  411.       table[ii] = n;
  412.       return n;
  413.       }
  414.     return 0;
  415. }
  416.  
  417. static Symtab *
  418. insert(const char *s)
  419. {
  420.     return lookup(s, 1);
  421. }
  422.  
  423.  
  424. /*************************************************************
  425.  * All supported function takes 1 double, and returns double
  426.  **************************************************************/
  427.  
  428. extern double cbrt(double);
  429. /***  Custom functions **/
  430.  
  431. static double
  432. deg(double d)
  433. {
  434.     return (d * 180.0 / M_PI);
  435. }
  436.  
  437. static double
  438. rad(double r)
  439. {
  440.     return (r * M_PI / 180.0);
  441. }
  442.  
  443.  
  444. /*******************************************************************
  445.  *  Structure holding all supported functions.
  446.  *  It would be nice to be able to check the validity of the
  447.  *  arguments
  448.  *******************************************************************/
  449.  
  450. typedef struct
  451. {
  452.     const char *fname;        /* function name        */
  453.     d1d_f mfunc;        /* the function         */
  454.     double lo, hi;        /* valid argument range */
  455. }
  456. d1d_t;
  457.  
  458.  
  459. /*
  460.  *  all double functions taking 1 double argument. if hi==lo,
  461.  *  any argument is ok
  462.  */
  463. static d1d_t d1d[] =
  464. {
  465.  /* trig functions */
  466.  
  467.     {"sin", sin, 0.0, 0.0},
  468.     {"cos", cos, 0.0, 0.0},
  469.     {"tan", tan, 0.0, 0.0},
  470.     {"acos", acos, -1.0, 1.0},
  471.     {"asin", asin, -1.0, 1.0},
  472.     {"atan", atan, 0.0, 0.0},
  473.  
  474.  /* roots, power etc */
  475.  
  476.     {"sqrt", sqrt, 0.0, HUGE},
  477.     {"cbrt", cbrt, 0.0, 0.0},
  478.     {"abs", fabs, 0.0, 0.0},
  479.  
  480.  /* exponetial and log */
  481.  
  482.     {"exp", exp, 0.0, 0.0},
  483.     {"log", log, 0.0, HUGE},
  484.     {"log10", log, 0.0, HUGE},
  485.  
  486.  /* misc functions */
  487.  
  488.     {"deg", deg, 0.0, 0.0},
  489.     {"rad", rad, 0.0, 0.0},
  490.  
  491.  /* special functions */
  492.  
  493.     {"j0", j0,},
  494.     {"j1", j1},
  495.     {"y0", y0},
  496.     {"y1", y1}
  497. };
  498.  
  499. static d1d_f
  500. search_func(const char *s)
  501. {
  502.     register d1d_t *dd = d1d + sizeof(d1d) / sizeof(d1d[0]);
  503.  
  504.     while (--dd >= d1d && strcmp(s, dd->fname))
  505.     ;
  506.     return (dd < d1d) ? 0 : dd->mfunc;
  507. }
  508.  
  509. #if 0                /* not used in bit */
  510. void
  511. list_builtin_functions(void)
  512. {
  513.     d1d_t *dd = d1d + sizeof(d1d) / sizeof(d1d[0]);
  514.     int n = 0;
  515.  
  516.     fprintf(stderr, "supported functions\n");
  517.     while (--dd >= d1d)
  518.       {
  519.       printf("%7s ", dd->fname);
  520.       if ((++n % 7) == 0)
  521.           putc('\n', stdout);
  522.       }
  523.     putc('\n', stdout);
  524. }
  525.  
  526. /* check if an argument is ok */
  527. int
  528. valid_arg(register d1d_f f, register double arg)
  529. {
  530.     register d1d_t *dd = d1d + sizeof(d1d) / sizeof(d1d[0]);
  531.  
  532.     while (--dd >= d1d && dd->mfunc != f)
  533.     ;
  534.  
  535.     return (dd->lo == dd->hi) ||
  536.     (arg > dd->lo && arg < dd->hi);
  537. }
  538.  
  539. #endif
  540.  
  541. #ifdef TEST
  542.  
  543. main()
  544. {
  545.     char in[1024];
  546.     static float x[2] =
  547.     {1.0, 2.0};
  548.     float y[2];
  549.     int i, status;
  550.  
  551.     while (fgets(in, 1024, stdin))
  552.       {
  553.       i = strlen(in) - 1;
  554.       in[i] = '\0';
  555.       if ((status = rd_evaluate(in, x, y, 2)))
  556.           fprintf(stderr, "error parsing %s\n", in);
  557.       else
  558.         {
  559.         fprintf(stderr, "For %s\n", in);
  560.         fprintf(stderr, "At x=%f %s=%g\n", x[0], in, y[0]);
  561.         fprintf(stderr, "At x=%f %s=%g\n", x[1], in, y[1]);
  562.         }
  563.       }
  564. }
  565. #endif
  566.